{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## I. Node\n",
    "\n",
    "----\n",
    "\n",
    "Xem thêm về [Node](https://www.tutorialspoint.com/python/python_nodes.htm)\n",
    "\n",
    "Một Node không chỉ chứa giá trị của Node đó mà còn chứa địa chỉ của phần từ tiếp theo nó\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Cách tạo 1 Node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://lh3.googleusercontent.com/TCwP9UEkLbD79ZfPoQkZ4RzUlCt4d4CseB5ZW_wkDKraywQveZZg6s41bvA51rqSMgddFBnJF0nQmLV2D4Kyo9b-fH195mQG56HstGHdDobkeERIBGUlLxGNwEUBxogx9WuKkywhdil-AwmfUIzo0Dhb4S5ZcrQiaQfSpWxqSk1wwvWOXlRG9Aef7H0SU1AsxA_6iZt9nOFF6a_4fEJvxjcJARfG6SLzjvu8PvF1Bg_hZXnryjx4jnAAYRaTzeOi6YBumuZF6UtenMu-ZhekNUwvkGU4jaJZZS2vzoMZe-b6og18F6L_h4_T-6Ccvym2oRmdT63EGTlR3Bv-nz6ULU8TurCB0veKr8Pu8xeetGw9CuonG1EJIoSwWqi-LMm2HtgFehF_ZJf2gmTevT6VM5oH_PR8oezMAAZ3csKx8yq0_NpOqQCz-qFV9mV1aEoh0ObF14PsePxwA9EJZGztgvCwpHFozvcrUopH0h5vuRF1ok4jT9G1RTG0cnRWVhVNwA-K6KDXo0lfSYv5-zAQ__xzf1CcZ1ZWHSXnQgTfZrDtGZHe2PxmEsbnFk-60WZPgbzRaV2ZqzTPuC5iu_2168SalwgG7CSi84yAKtrNOFIyvpw3ZVoaQ2xMkUIS1UZEOLjBpczvYulePi6QaNlGuFffIioC7DtdOg=w800-h400-no)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ta tạo ra 1 Class có 2 biến thực thế (instance variable).\n",
    "    - 1 là val sẽ chứa giá trị của thực thể đó\n",
    "    - 2 là nextVal sẽ trỏ đến thực thể kế tiếp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 235,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Number:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.nextVal = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 236,
   "metadata": {},
   "outputs": [],
   "source": [
    "number1 = Number(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 237,
   "metadata": {},
   "outputs": [],
   "source": [
    "number2 = Number(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "metadata": {},
   "outputs": [],
   "source": [
    "number3 = Number(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 239,
   "metadata": {},
   "outputs": [],
   "source": [
    "number1.nextVal = number2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 240,
   "metadata": {},
   "outputs": [],
   "source": [
    "number2.nextVal = number3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Truy cập giá trị của các node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 241,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 241,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Từ number1 truy cập giá trị của nmber2\n",
    "number1.nextVal.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 242,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Từ number1 truy cập giá trị của number3\n",
    "number1.nextVal.nextVal.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 243,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Từ number2 truy cập giá trị của number3\n",
    "number2.nextVal.val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Đọc toàn bộ dữ liệu của các node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 244,
   "metadata": {},
   "outputs": [],
   "source": [
    "currentNode = number1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 245,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "while currentNode:\n",
    "    print currentNode.val\n",
    "    currentNode = currentNode.nextVal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## II. Linked List\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Xem thêm về [Linked List](https://www.tutorialspoint.com/python/python_linked_lists.htm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Linked List là chuỗi các phần tử mà tất cả được kết nối với nhau thông qua các liên kết(link). Mỗi phần tử ngoài việc lưu trữ giá trị của mình, nó còn lưu thêm vị trí của phần tử kế tiếp nó. \n",
    "\n",
    "Bản chất ta có thể thấy Linked List là chuỗi được ghép bởi các **Node** ta đã thực hiện ở phía trên"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 299,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implement lại Node\n",
    "class Number:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.nextVal = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 300,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "instance"
      ]
     },
     "execution_count": 300,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "number1 = Number(1)\n",
    "number2 = Number(2)\n",
    "number3 = Number(3)\n",
    "\n",
    "type(number1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 301,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        # biến thực thể head đại diện cho Node ở đầu List\n",
    "        self.head = None\n",
    "        \n",
    "    # Hàm in tất cả các giá trị trong List\n",
    "    def printVal(self):\n",
    "        currentNode = self.head\n",
    "        while currentNode:\n",
    "            print currentNode.val\n",
    "            currentNode = currentNode.nextVal\n",
    "            \n",
    "    # Thêm một Node vào cuối cùng của List\n",
    "    def appendNode(self, node):\n",
    "        if isinstance(node, Number):\n",
    "            currentNode = self.head\n",
    "            # Lặp qua tất cả các Node. \n",
    "            # Nếu Node tiếp theo tồn tại thì di chuyển vị trí hiện tại sang Node tiếp theo\n",
    "            # Nếu Node tiếp theo không tồn tại thì thêm Node mới\n",
    "            while currentNode:\n",
    "                if currentNode.nextVal is not None:\n",
    "                    currentNode = currentNode.nextVal\n",
    "                else:\n",
    "                    currentNode.nextVal = node\n",
    "                    break\n",
    "        else:\n",
    "            raise ValueError(\"This is not Number Node type.\") \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 302,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Khởi tạo một Linked List\n",
    "list1 = LinkedList()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 303,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Đặt đầu List là Node number1\n",
    "list1.head = number1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 304,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Nối Node đầu với Node thứ hai\n",
    "number1.nextVal = number2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 305,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Nối Node thứ hai với Node thứ ba\n",
    "number2.nextVal = number3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 306,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 306,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# In giá trị của Node thứ ba\n",
    "list1.head.nextVal.nextVal.val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 307,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# In tất cả các giá trị trong List\n",
    "list1.printVal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 308,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Thêm một Node có giá trị 4 vào cuối List\n",
    "number4 = Number(4)\n",
    "list1.appendNode(number4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 309,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# Kiểm tra lại giá trị của List\n",
    "list1.printVal()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
